class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */

     // 这个算法的巧妙之处就是很好处理了当回文中心为偶数的情况
 // 从str的第0个开始，     
    int getLongestPalindrome(string A) {
        // write code here
        int res = 0, step;
        for (int i = 0; i < A.size(); i ++)
        {
            int l = i - 1, r = i + 1;
            step = 1;
            while (r < A.size() && A[i] == A[r])
            {
                ++r;
            }
            while (l >= 0 && r < A.size() && A[l] == A[r])
            {
                ++r;
                --l;
            }
            res = max(res, r-l-1); //这里的的-1是有必要的的 因为第一个while里面相等之后就会r++一次 ，另一方面，第二个while也是相等了会l-- r++一次，只能说设计的妙
        }
        return res;
    }
};


void fun(){

    for(int i=0; i< str.size; i++){
        int l = i -1;
        int r = i + 1;
        while(r<str.size() && str[i] < str[r]){
                r++;
        }

        return max(Len, r - l)

    }

}




class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        if(len==0||len==1)
            return s;
        int start=0;//记录回文子串起始位置
        int end=0;//记录回文子串终止位置
        int mlen=0;//记录最大回文子串的长度
        for(int i=0;i<len;i++)
        {
            int len1=expendaroundcenter(s,i,i);//一个元素为中心
            int len2=expendaroundcenter(s,i,i+1);//两个元素为中心
            mlen=max(max(len1,len2),mlen);
            if(mlen>end-start+1)
            {
                start=i-(mlen-1)/2;
                end=i+mlen/2;
            }
        }
        return s.substr(start,mlen);
        //该函数的意思是获取从start开始长度为mlen长度的字符串
    }
private:
    int expendaroundcenter(string s,int left,int right)
    //计算以left和right为中心的回文串长度
    {
        int L=left;
        int R=right;
        while(L>=0 && R<s.length() && s[R]==s[L])
        {
            L--;
            R++;
        }
        return R-L-1;
    }
};




class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        vector<vector<int>> dp(n,vector<int>(n,0));
        int m=n/2+1;
        int maxLength=0;
        for(int d=0;d<=m;d++)   //尝试递增判断步长，当前一步是满足的，可递增下一个 dp[i][j]表示第j个位置的字符，向两边扩充字符时，，
        {                            //size为i（即不断变化的d）时是否符合回文，如当前不合符，以后的更不能符合
            for(int i=0;i<n-d;i++)   ///只需要小于n-d就可以了
            {                         //注意，向两边扩充总是避免不了奇偶判断，故采用
               if(A[i]==A[i+d])   //如果字符的两边对称相等
               {
                if(d==0||d==1)                //i 到 j 的首尾相等，再根据字符串 i-1 到 j-1 来确定，即得到递推公式
                {
                    dp[i][i+d]=1;
                }
                else
                {
                    dp[i][i+d]=dp[i+1][i+d-1];  //true 的传递性
                }
                   if(dp[i][i+d])   //  只有为真才更新最长
                   {
                   maxLength=max(maxLength,d+1); // 注意这里是d+1
                   }
               }
            }
            
        }
        return maxLength;
         
    
    }
};